CS 320 -- Midterm Study Guide

Practice Problems and Solutions 2 A Alternate

These problems are offered to help understand the lecture material and assist with completing homeworks; they will also form the basis for some problems on the midterms. They are entirely optional, and feel free to skip if you understand a concept!

You should do these problems on paper or mentally first, and only THEN check the solution.

This set of problems uses the built-in Haskell notations for tuples and lists; for a version of the same problems using BB Haskell, with explicit definitions for Pairs and Lists see here.

2. BareBones Haskell: Types and type checking

Consider the following data declaration:

data D a = A Integer | B Bool | C a 
data Nat = Zero | Succ Nat
data Tree a = Null | Node (Tree a) a (Tree a)

For the first part of these exercises, we will ask you to give the types of various constructors in the above data declarations; then we will define some functions using these data, plus Integer and Bool, and you will need to give the types of the functions, as well as some expressions involving these functions.

We assume that we can have Integer and Bools as defined in the Haskell Prelude. Assume for the purposes of these exercises that all arithmetic operators operate only on Integers, so pretend the type of (+) is:

 (+): Integer -> Integer -> Integer.

If the expression is an error, explain where the error occurs.

Constructors

Give the type of the following constructors.

2.1. Zero

Zero :: Nat

Hint: You can check the type of expressions and symbols by using
the following:

Main> :type Zero       -- can also use the abbreviation  :t
Zero :: Nat

2.2. Succ

Succ :: Nat -> Nat

2.3. B

B :: Bool -> D a

2.4. C

C :: a -> D a

2.5. (:)

(:) :: a -> [a] -> [a]

2.6. []

[] :: [a]

2.7. Node

Node :: Tree a -> a -> Tree a -> Tree a

Constructor Expressions (with Integer and Bool)

Give the type of the following expressions

2.8. (Succ Zero)

(Succ Zero) :: Nat

2.9. C 6

C 6 :: D Integer

Note that if you try this in the REPL, you will get:

*Main> :t C 9
C 9 :: Num a => D a

which says that a can be any "numeric type". We will talk
about what this means when we study type classes. For
this set of exercises, we will assume that all such
types are simple Integer, hence our answer.

2.10. (5, True)

(5, True)  :: (Integer, Bool)

2.11. C (4, (A 5))

C (4, (A 5)) :: D (Integer, (D a2))

2.12. C (C (B True))

C (C (B True)) :: D (D (D a))

2.13. ((9, 1), ((C 0), True))

((9, 1), ((C 0), True)):: ((Integer, Integer), ((D Integer), Bool))

2.14. [(C 4),(A 5)]

[(C 4),(A 5)] :: [D Integer]

2.15. [ [ True ] ]

[ [True] ] :: [[Bool]]

2.16. Node Null [2] Null

Node Null [2] Null :: Tree [Integer]

2.17. C (Node Null [ (C (3, 0)) ] Null)

C (Node Null [ (C (3, 0)) ] Null) :: D (Tree [D (Integer, Integer)])

Types Involving Constructors and Functions

Suppose for this section that in addition to the data declarations above, we have the following data and function definitions. (The types Either and Maybe are defined in the Prelude and used very often in Haskell programming.)

data Either a b = Left a | Right b
data Maybe a = Nothing | Just a

safeHead []    = Nothing
safeHead (x:_) = Just x

safeTail []     = Nothing
safeTail (_:xs) = Just xs

fst (x,_) = x
snd (_,y) = y

f (x,y) = x + y

g (True,x)  = Left x
g (False,y) = Right y

For the next seven problems, just give the types of the functions just defined. The last four will be simple polymorphic types.

2.18. f

2.19. g

g :: (Bool,a) -> Either a a

Function h has been eliminated, along with problem 2.20.

2.21. safeHead

safeHead :: [a] -> Maybe a

2.22. safeTail

safeTail :: [a] -> Maybe ([a])

2.23. fst

fst :: (a,b) -> a

2.24. snd

snd :: (a,b) -> b

Give the types of the following expressions. If the expression can not be typed, explain why.

2.25. g ((not True), (f (4, 5)))

g ((not True), (f (4, 5))) :: Either Integer Integer

2.26. fst (0, (g (True, True))))

fst (0, (g (True, True))) :: Integer

2.27. safeHead [(fst (3,True)),0]

safeHead [(fst (3,True)),0] :: Maybe Integer

2.28. safeHead (safeTail [(fst (3, True)), 0])

The expression can not be typed. The expression

(safeTail [(fst (3, True)), 0])

has type 

Maybe [ Integer ]

and safeHead requires [a].

2.29.

  g ((fst x), (snd x))
      where x = ((snd (3, True)), (False, 5))

The expression has type Either (Bool, Integer) (Bool, Integer)

2.30.

 g ((snd x), (fst x))
      where x = ((snd (3,True)) ,(False, 5))

No, it doesn't type check: the expression (snd x) has
type

(Bool, Integer)

and g expects a type (Bool, a), and Bool != (Bool,Integer)

2.31.

 g ((fst x), (fst x))
      where x = ((snd (3, True)), (False, 5))

The expression has type  Either Bool Bool.